﻿using System.Collections.Generic;

namespace Go
{
    public class Map<TKey, TValue>
    {
        public class Node
        {
            internal const bool state0 = false;
            internal const bool state1 = true;

            internal Node left;
            internal Node right;
            internal Node parent;
            internal TKey key;
            internal TValue value;
            internal bool state;

            internal Node()
            {
            }

            public TKey Key
            {
                get
                {
                    return key;
                }
            }

            public TValue Value
            {
                get
                {
                    return value;
                }
                set
                {
                    this.value = value;
                }
            }

            public bool Isolated
            {
                get
                {
                    return null == parent;
                }
            }

            public override string ToString()
            {
                return string.Format("({0},{1})", key, value);
            }
        }

        int _count;
        int _change;
        readonly Node _head;
        readonly bool _multi;

        public Map(bool multi = false)
        {
            _count = 0;
            _change = 0;
            _multi = multi;
            _head = new Node();
            _head.state = Node.state0;
            root = lmost = rmost = _head;
        }

        static public Node NewNode(TKey key, TValue value)
        {
            return new Node() { key = key, value = value, state = Node.state1 };
        }

        public Node ReNewNode(Node oldNode, TKey key, TValue value)
        {
            if (!oldNode.Isolated)
            {
                Remove(oldNode);
            }
            oldNode.key = key;
            oldNode.value = value;
            oldNode.state = Node.state1;
            return oldNode;
        }

        static bool comp_lt<T>(T x, T y)
        {
            return Comparer<T>.Default.Compare(x, y) < 0;
        }

        bool is_nil(Node node)
        {
            return node == _head;
        }

        Node root
        {
            get
            {
                return _head.parent;
            }
            set
            {
                _head.parent = value;
            }
        }

        Node lmost
        {
            get
            {
                return _head.left;
            }
            set
            {
                _head.left = value;
            }
        }

        Node rmost
        {
            get
            {
                return _head.right;
            }
            set
            {
                _head.right = value;
            }
        }

        void left_rotate(Node whereNode)
        {
            Node pNode = whereNode.right;
            whereNode.right = pNode.left;
            if (!is_nil(pNode.left))
            {
                pNode.left.parent = whereNode;
            }
            pNode.parent = whereNode.parent;
            if (whereNode == root)
            {
                root = pNode;
            }
            else if (whereNode == whereNode.parent.left)
            {
                whereNode.parent.left = pNode;
            }
            else
            {
                whereNode.parent.right = pNode;
            }
            pNode.left = whereNode;
            whereNode.parent = pNode;
        }

        void right_rotate(Node whereNode)
        {
            Node pNode = whereNode.left;
            whereNode.left = pNode.right;
            if (!is_nil(pNode.right))
            {
                pNode.right.parent = whereNode;
            }
            pNode.parent = whereNode.parent;
            if (whereNode == root)
            {
                root = pNode;
            }
            else if (whereNode == whereNode.parent.right)
            {
                whereNode.parent.right = pNode;
            }
            else
            {
                whereNode.parent.left = pNode;
            }
            pNode.right = whereNode;
            whereNode.parent = pNode;
        }

        void insert_at(bool addLeft, Node whereNode, Node newNode)
        {
            _change++;
            newNode.parent = whereNode;
            if (whereNode == _head)
            {
                root = lmost = rmost = newNode;
            }
            else if (addLeft)
            {
                whereNode.left = newNode;
                if (whereNode == lmost)
                {
                    lmost = newNode;
                }
            }
            else
            {
                whereNode.right = newNode;
                if (whereNode == rmost)
                {
                    rmost = newNode;
                }
            }
            for (Node pNode = newNode; Node.state1 == pNode.parent.state;)
            {
                if (pNode.parent == pNode.parent.parent.left)
                {
                    whereNode = pNode.parent.parent.right;
                    if (Node.state1 == whereNode.state)
                    {
                        pNode.parent.state = Node.state0;
                        whereNode.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        pNode = pNode.parent.parent;
                    }
                    else
                    {
                        if (pNode == pNode.parent.right)
                        {
                            pNode = pNode.parent;
                            left_rotate(pNode);
                        }
                        pNode.parent.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        right_rotate(pNode.parent.parent);
                    }
                }
                else
                {
                    whereNode = pNode.parent.parent.left;
                    if (Node.state1 == whereNode.state)
                    {
                        pNode.parent.state = Node.state0;
                        whereNode.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        pNode = pNode.parent.parent;
                    }
                    else
                    {
                        if (pNode == pNode.parent.left)
                        {
                            pNode = pNode.parent;
                            right_rotate(pNode);
                        }
                        pNode.parent.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        left_rotate(pNode.parent.parent);
                    }
                }
            }
            root.state = Node.state0;
            _count++;
        }

        void insert(Node newNode, bool priorityRight)
        {
            newNode.parent = newNode.left = newNode.right = _head;
            Node tryNode = root;
            Node whereNode = _head;
            bool addLeft = true;
            while (!is_nil(tryNode))
            {
                whereNode = tryNode;
                addLeft = priorityRight ? comp_lt(newNode.key, tryNode.key) : !comp_lt(tryNode.key, newNode.key);
                tryNode = addLeft ? tryNode.left : tryNode.right;
            }
            if (_multi)
            {
                insert_at(addLeft, whereNode, newNode);
            }
            else
            {
                Node where = whereNode;
                if (!addLeft) { }
                else if (where == lmost)
                {
                    insert_at(true, whereNode, newNode);
                    return;
                }
                else
                {
                    where = previous(where);
                }
                if (comp_lt(where.key, newNode.key))
                {
                    insert_at(addLeft, whereNode, newNode);
                }
                else
                {
                    newNode.parent = newNode.left = newNode.right = null;
                }
            }
        }

        Node new_inter_node(TKey key, TValue value)
        {
            Node newNode = NewNode(key, value);
            newNode.parent = newNode.left = newNode.right = _head;
            return newNode;
        }

        Node insert(TKey key, TValue value, bool priorityRight)
        {
            Node tryNode = root;
            Node whereNode = _head;
            bool addLeft = true;
            while (!is_nil(tryNode))
            {
                whereNode = tryNode;
                addLeft = priorityRight ? comp_lt(key, tryNode.key) : !comp_lt(tryNode.key, key);
                tryNode = addLeft ? tryNode.left : tryNode.right;
            }
            Node newNode = null;
            if (_multi)
            {
                newNode = new_inter_node(key, value);
                insert_at(addLeft, whereNode, newNode);
            }
            else
            {
                Node where = whereNode;
                if (!addLeft) { }
                else if (where == lmost)
                {
                    newNode = new_inter_node(key, value);
                    insert_at(true, whereNode, newNode);
                    return newNode;
                }
                else
                {
                    where = previous(where);
                }
                if (comp_lt(where.key, key))
                {
                    newNode = new_inter_node(key, value);
                    insert_at(addLeft, whereNode, newNode);
                }
            }
            return newNode;
        }

        void remove(Node where)
        {
            _change++;
            Node erasedNode = where;
            where = next(where);
            Node fixNode = null;
            Node fixNodeParent = null;
            Node pNode = erasedNode;
            if (is_nil(pNode.left))
            {
                fixNode = pNode.right;
            }
            else if (is_nil(pNode.right))
            {
                fixNode = pNode.left;
            }
            else
            {
                pNode = where;
                fixNode = pNode.right;
            }
            if (pNode == erasedNode)
            {
                fixNodeParent = erasedNode.parent;
                if (!is_nil(fixNode))
                {
                    fixNode.parent = fixNodeParent;
                }
                if (root == erasedNode)
                {
                    root = fixNode;
                }
                else if (fixNodeParent.left == erasedNode)
                {
                    fixNodeParent.left = fixNode;
                }
                else
                {
                    fixNodeParent.right = fixNode;
                }
                if (lmost == erasedNode)
                {
                    lmost = is_nil(fixNode) ? fixNodeParent : min(fixNode);
                }
                if (rmost == erasedNode)
                {
                    rmost = is_nil(fixNode) ? fixNodeParent : max(fixNode);
                }
            }
            else
            {
                erasedNode.left.parent = pNode;
                pNode.left = erasedNode.left;
                if (pNode == erasedNode.right)
                {
                    fixNodeParent = pNode;
                }
                else
                {
                    fixNodeParent = pNode.parent;
                    if (!is_nil(fixNode))
                    {
                        fixNode.parent = fixNodeParent;
                    }
                    fixNodeParent.left = fixNode;
                    pNode.right = erasedNode.right;
                    erasedNode.right.parent = pNode;
                }
                if (root == erasedNode)
                {
                    root = pNode;
                }
                else if (erasedNode.parent.left == erasedNode)
                {
                    erasedNode.parent.left = pNode;
                }
                else
                {
                    erasedNode.parent.right = pNode;
                }
                pNode.parent = erasedNode.parent;
                bool tcol = pNode.state;
                pNode.state = erasedNode.state;
                erasedNode.state = tcol;
            }
            if (Node.state0 == erasedNode.state)
            {
                for (; fixNode != root && Node.state0 == fixNode.state; fixNodeParent = fixNode.parent)
                {
                    if (fixNode == fixNodeParent.left)
                    {
                        pNode = fixNodeParent.right;
                        if (Node.state1 == pNode.state)
                        {
                            pNode.state = Node.state0;
                            fixNodeParent.state = Node.state1;
                            left_rotate(fixNodeParent);
                            pNode = fixNodeParent.right;
                        }
                        if (is_nil(pNode))
                        {
                            fixNode = fixNodeParent;
                        }
                        else if (Node.state0 == pNode.left.state && Node.state0 == pNode.right.state)
                        {
                            pNode.state = Node.state1;
                            fixNode = fixNodeParent;
                        }
                        else
                        {
                            if (Node.state0 == pNode.right.state)
                            {
                                pNode.left.state = Node.state0;
                                pNode.state = Node.state1;
                                right_rotate(pNode);
                                pNode = fixNodeParent.right;
                            }
                            pNode.state = fixNodeParent.state;
                            fixNodeParent.state = Node.state0;
                            pNode.right.state = Node.state0;
                            left_rotate(fixNodeParent);
                            break;
                        }
                    }
                    else
                    {
                        pNode = fixNodeParent.left;
                        if (Node.state1 == pNode.state)
                        {
                            pNode.state = Node.state0;
                            fixNodeParent.state = Node.state1;
                            right_rotate(fixNodeParent);
                            pNode = fixNodeParent.left;
                        }
                        if (is_nil(pNode))
                        {
                            fixNode = fixNodeParent;
                        }
                        else if (Node.state0 == pNode.right.state && Node.state0 == pNode.left.state)
                        {
                            pNode.state = Node.state1;
                            fixNode = fixNodeParent;
                        }
                        else
                        {
                            if (Node.state0 == pNode.left.state)
                            {
                                pNode.right.state = Node.state0;
                                pNode.state = Node.state1;
                                left_rotate(pNode);
                                pNode = fixNodeParent.left;
                            }
                            pNode.state = fixNodeParent.state;
                            fixNodeParent.state = Node.state0;
                            pNode.left.state = Node.state0;
                            right_rotate(fixNodeParent);
                            break;
                        }
                    }
                }
                fixNode.state = Node.state0;
            }
            erasedNode.parent = erasedNode.left = erasedNode.right = null;
            _count--;
        }

        Node lbound(TKey key)
        {
            Node pNode = root;
            Node whereNode = _head;
            while (!is_nil(pNode))
            {
                if (comp_lt(pNode.key, key))
                {
                    pNode = pNode.right;
                }
                else
                {
                    whereNode = pNode;
                    pNode = pNode.left;
                }
            }
            return whereNode;
        }

        Node rbound(TKey key)
        {
            Node pNode = root;
            Node whereNode = _head;
            while (!is_nil(pNode))
            {
                if (comp_lt(key, pNode.key))
                {
                    pNode = pNode.left;
                }
                else
                {
                    whereNode = pNode;
                    pNode = pNode.right;
                }
            }
            return whereNode;
        }

        tuple<bool, Node> lbound_insert(TKey key)
        {
            Node pNode = root;
            Node insertWhereNode = _head;
            Node boundWhereNode = _head;
            bool addLeft = true;
            while (!is_nil(pNode))
            {
                insertWhereNode = pNode;
                if (comp_lt(pNode.key, key))
                {
                    addLeft = false;
                    pNode = pNode.right;
                }
                else
                {
                    addLeft = true;
                    boundWhereNode = pNode;
                    pNode = pNode.left;
                }
            }
            if (!is_nil(boundWhereNode) && !comp_lt(key, boundWhereNode.key))
            {
                return tuple.make(true, boundWhereNode);
            }
            Node newNode = new_inter_node(key, default(TValue));
            insert_at(addLeft, insertWhereNode, newNode);
            return tuple.make(false, newNode);
        }

        tuple<bool, Node> rbound_insert(TKey key)
        {
            Node pNode = root;
            Node insertWhereNode = _head;
            Node boundWhereNode = _head;
            bool addLeft = true;
            while (!is_nil(pNode))
            {
                insertWhereNode = pNode;
                if (comp_lt(key, pNode.key))
                {
                    addLeft = false;
                    pNode = pNode.left;
                }
                else
                {
                    addLeft = true;
                    boundWhereNode = pNode;
                    pNode = pNode.right;
                }
            }
            if (!is_nil(boundWhereNode) && !comp_lt(boundWhereNode.key, key))
            {
                return tuple.make(true, boundWhereNode);
            }
            Node newNode = new_inter_node(key, default(TValue));
            insert_at(addLeft, insertWhereNode, newNode);
            return tuple.make(false, newNode);
        }

        Node max(Node pNode)
        {
            while (!is_nil(pNode.right))
            {
                pNode = pNode.right;
            }
            return pNode;
        }

        Node min(Node pNode)
        {
            while (!is_nil(pNode.left))
            {
                pNode = pNode.left;
            }
            return pNode;
        }

        Node next(Node ptr)
        {
            if (is_nil(ptr))
            {
                return ptr;
            }
            else if (!is_nil(ptr.right))
            {
                return min(ptr.right);
            }
            else
            {
                Node pNode;
                while (!is_nil(pNode = ptr.parent) && ptr == pNode.right)
                {
                    ptr = pNode;
                }
                return pNode;
            }
        }

        Node previous(Node ptr)
        {
            if (is_nil(ptr))
            {
                return ptr;
            }
            else if (!is_nil(ptr.left))
            {
                return max(ptr.left);
            }
            else
            {
                Node pNode;
                while (!is_nil(pNode = ptr.parent) && ptr == pNode.left)
                {
                    ptr = pNode;
                }
                return pNode;
            }
        }

        void erase(Node rootNode)
        {
            for (Node pNode = rootNode; !is_nil(pNode); rootNode = pNode)
            {
                erase(pNode.right);
                pNode = pNode.left;
                rootNode.parent = rootNode.left = rootNode.right = null;
            }
        }

        public int Count
        {
            get
            {
                return _count;
            }
        }

        public void Clear()
        {
            _change++;
            erase(root);
            root = lmost = rmost = _head;
            _count = 0;
        }

        public Node FindFirstGE(TKey key)
        {
            Node node = lbound(key);
            return !is_nil(node) ? node : null;
        }

        public Node FindFirstLE(TKey key)
        {
            Node node = rbound(key);
            return !is_nil(node) ? node : null;
        }

        public Node FindFirst(TKey key)
        {
            Node node = lbound(key);
            return !is_nil(node) && !comp_lt(key, node.key) ? node : null;
        }

        public Node FindLast(TKey key)
        {
            Node node = rbound(key);
            return !is_nil(node) && !comp_lt(node.key, key) ? node : null;
        }

        public Node FindRight(TKey key)
        {
            Node node = lbound(key);
            return is_nil(node) ? null : node;
        }

        public Node FindLeft(TKey key)
        {
            Node node = rbound(key);
            return is_nil(node) ? null : node;
        }

        public tuple<bool, Node> GetFirst(TKey key)
        {
            return lbound_insert(key);
        }

        public tuple<bool, Node> GetLast(TKey key)
        {
            return rbound_insert(key);
        }

        public void Remove(Node node)
        {
            remove(node);
        }

        public Node Next(Node node)
        {
            node = next(node);
            return is_nil(node) ? null : node;
        }

        public Node Prev(Node node)
        {
            node = previous(node);
            return is_nil(node) ? null : node;
        }

        public Node Insert(TKey key, TValue value, bool priorityRight = true)
        {
            return insert(key, value, _multi ? priorityRight : true);
        }

        public bool Insert(Node newNode, bool priorityRight = true)
        {
            insert(newNode, _multi ? priorityRight : true);
            return !newNode.Isolated;
        }

        public IEnumerator<tuple<TKey, TValue>> GetEnumerator()
        {
            int change = _change;
            Node it = lmost;
            while (!is_nil(it))
            {
                yield return tuple.make(it.key, it.value);
                if (change != _change)
                {
                    break;
                }
                it = next(it);
            }
            yield break;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            Node node = FindFirst(key);
            if (null == node)
            {
                value = default;
                return false;
            }
            value = node.value;
            return true;
        }

        public bool ContainsKey(TKey key)
        {
            return null != FindFirst(key);
        }

        public bool Remove(TKey key)
        {
            Node node = FindFirst(key);
            if (null == node)
            {
                return false;
            }
            Remove(node);
            return true;
        }

        public bool Remove(TKey key, out TValue value)
        {
            Node node = FindFirst(key);
            if (null == node)
            {
                value = default;
                return false;
            }
            value = node.value;
            Remove(node);
            return true;
        }

        public bool Add(TKey key, TValue value)
        {
            return null != Insert(key, value);
        }

        public tuple<TKey, TValue>[] ToArray()
        {
            int idx = 0;
            tuple<TKey, TValue>[] array = new tuple<TKey, TValue>[_count];
            Node it = lmost;
            while (!is_nil(it))
            {
                array[idx++] = tuple.make(it.key, it.value);
                it = next(it);
            }
            return array;
        }

        public List<tuple<TKey, TValue>> ToList()
        {
            List<tuple<TKey, TValue>> list = new List<tuple<TKey, TValue>>(_count);
            Node it = lmost;
            while (!is_nil(it))
            {
                list.Add(tuple.make(it.key, it.value));
                it = next(it);
            }
            return list;
        }

        public Node First
        {
            get
            {
                return is_nil(lmost) ? null : lmost;
            }
        }

        public Node Last
        {
            get
            {
                return is_nil(rmost) ? null : rmost;
            }
        }
    }

    public class MapList<TValue>
    {
        public class Node
        {
            internal const bool state0 = false;
            internal const bool state1 = true;

            internal Node left;
            internal Node right;
            internal Node parent;
            internal TValue value;
            internal int lnum;
            internal int rnum;
            internal bool state;

            internal Node()
            {
            }

            public TValue Value
            {
                get
                {
                    return value;
                }
                set
                {
                    this.value = value;
                }
            }

            public override string ToString()
            {
                return value.ToString();
            }
        }

        int _change;
        readonly Node _head;

        public MapList()
        {
            _change = 0;
            _head = new Node();
            _head.state = Node.state0;
            root = lmost = rmost = _head;
        }

        static public Node NewNode(TValue value)
        {
            return new Node { value = value, state = Node.state1 };
        }

        bool is_nil(Node node)
        {
            return node == _head;
        }

        Node root
        {
            get
            {
                return _head.parent;
            }
            set
            {
                _head.parent = value;
            }
        }

        Node lmost
        {
            get
            {
                return _head.left;
            }
            set
            {
                _head.left = value;
            }
        }

        Node rmost
        {
            get
            {
                return _head.right;
            }
            set
            {
                _head.right = value;
            }
        }

        void left_rotate(Node whereNode)
        {
            Node pNode = whereNode.right;
            whereNode.right = pNode.left;
            if (!is_nil(pNode.left))
            {
                pNode.left.parent = whereNode;
            }
            pNode.parent = whereNode.parent;
            if (whereNode == root)
            {
                root = pNode;
            }
            else if (whereNode == whereNode.parent.left)
            {
                whereNode.parent.left = pNode;
            }
            else
            {
                whereNode.parent.right = pNode;
            }
            pNode.left = whereNode;
            whereNode.parent = pNode;
            whereNode.rnum = pNode.lnum + 1;
            pNode.lnum = whereNode.lnum + whereNode.rnum;
        }

        void right_rotate(Node whereNode)
        {
            Node pNode = whereNode.left;
            whereNode.left = pNode.right;
            if (!is_nil(pNode.right))
            {
                pNode.right.parent = whereNode;
            }
            pNode.parent = whereNode.parent;
            if (whereNode == root)
            {
                root = pNode;
            }
            else if (whereNode == whereNode.parent.right)
            {
                whereNode.parent.right = pNode;
            }
            else
            {
                whereNode.parent.left = pNode;
            }
            pNode.right = whereNode;
            whereNode.parent = pNode;
            whereNode.lnum = pNode.rnum - 1;
            pNode.rnum = whereNode.rnum + whereNode.lnum + 1;
        }

        void inc_num(Node newNode)
        {
            newNode.lnum = 0;
            newNode.rnum = 1;
            Node pNode = newNode;
            while (!is_nil(pNode) && !is_nil(pNode.parent))
            {
                if (pNode == pNode.parent.left)
                {
                    pNode.parent.lnum++;
                }
                else
                {
                    pNode.parent.rnum++;
                }
                pNode = pNode.parent;
            }
        }

        void insert_at(bool addLeft, Node whereNode, Node newNode)
        {
            _change++;
            newNode.parent = whereNode;
            if (whereNode == _head)
            {
                root = lmost = rmost = newNode;
            }
            else if (addLeft)
            {
                whereNode.left = newNode;
                if (whereNode == lmost)
                {
                    lmost = newNode;
                }
            }
            else
            {
                whereNode.right = newNode;
                if (whereNode == rmost)
                {
                    rmost = newNode;
                }
            }
            inc_num(newNode);
            for (Node pNode = newNode; Node.state1 == pNode.parent.state;)
            {
                if (pNode.parent == pNode.parent.parent.left)
                {
                    whereNode = pNode.parent.parent.right;
                    if (Node.state1 == whereNode.state)
                    {
                        pNode.parent.state = Node.state0;
                        whereNode.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        pNode = pNode.parent.parent;
                    }
                    else
                    {
                        if (pNode == pNode.parent.right)
                        {
                            pNode = pNode.parent;
                            left_rotate(pNode);
                        }
                        pNode.parent.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        right_rotate(pNode.parent.parent);
                    }
                }
                else
                {
                    whereNode = pNode.parent.parent.left;
                    if (Node.state1 == whereNode.state)
                    {
                        pNode.parent.state = Node.state0;
                        whereNode.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        pNode = pNode.parent.parent;
                    }
                    else
                    {
                        if (pNode == pNode.parent.left)
                        {
                            pNode = pNode.parent;
                            right_rotate(pNode);
                        }
                        pNode.parent.state = Node.state0;
                        pNode.parent.parent.state = Node.state1;
                        left_rotate(pNode.parent.parent);
                    }
                }
            }
            root.state = Node.state0;
        }

        void insert(int index, Node newNode)
        {
            newNode.parent = newNode.left = newNode.right = _head;
            Node tryNode = root;
            Node whereNode = _head;
            bool addLeft = true;
            int leftCount = 0;
            while (!is_nil(tryNode))
            {
                whereNode = tryNode;
                if (index <= leftCount + tryNode.lnum)
                {
                    addLeft = true;
                    tryNode = tryNode.left;
                }
                else
                {
                    addLeft = false;
                    leftCount += tryNode.lnum + 1;
                    tryNode = tryNode.right;
                }
            }
            insert_at(addLeft, whereNode, newNode);
        }

        Node new_inter_node(TValue value)
        {
            Node newNode = NewNode(value);
            newNode.parent = newNode.left = newNode.right = _head;
            return newNode;
        }

        Node insert(int index, TValue value)
        {
            Node newNode = new_inter_node(value);
            insert(index, newNode);
            return newNode;
        }

        void dec_num(Node newNode)
        {
            Node pNode = newNode;
            while (!is_nil(pNode) && !is_nil(pNode.parent))
            {
                if (pNode == pNode.parent.left)
                {
                    pNode.parent.lnum--;
                }
                else
                {
                    pNode.parent.rnum--;
                }
                pNode = pNode.parent;
            }
        }

        void remove(Node where)
        {
            _change++;
            Node erasedNode = where;
            where = next(where);
            Node fixNode;
            Node fixNodeParent;
            Node pNode = erasedNode;
            if (is_nil(pNode.left))
            {
                fixNode = pNode.right;
            }
            else if (is_nil(pNode.right))
            {
                fixNode = pNode.left;
            }
            else
            {
                pNode = where;
                fixNode = pNode.right;
            }
            if (pNode == erasedNode)
            {
                fixNodeParent = erasedNode.parent;
                if (!is_nil(fixNode))
                {
                    fixNode.parent = fixNodeParent;
                }
                if (root == erasedNode)
                {
                    root = fixNode;
                }
                else if (fixNodeParent.left == erasedNode)
                {
                    fixNodeParent.left = fixNode;
                    fixNodeParent.lnum--;
                }
                else
                {
                    fixNodeParent.right = fixNode;
                    fixNodeParent.rnum--;
                }
                dec_num(fixNodeParent);
                if (lmost == erasedNode)
                {
                    lmost = is_nil(fixNode) ? fixNodeParent : min(fixNode);
                }
                if (rmost == erasedNode)
                {
                    rmost = is_nil(fixNode) ? fixNodeParent : max(fixNode);
                }
            }
            else
            {
                erasedNode.left.parent = pNode;
                pNode.left = erasedNode.left;
                if (pNode == erasedNode.right)
                {
                    fixNodeParent = pNode;
                    pNode.lnum = erasedNode.lnum;
                }
                else
                {
                    fixNodeParent = pNode.parent;
                    if (!is_nil(fixNode))
                    {
                        fixNode.parent = fixNodeParent;
                    }
                    fixNodeParent.left = fixNode;
                    pNode.right = erasedNode.right;
                    erasedNode.right.parent = pNode;
                    pNode.rnum = erasedNode.rnum;
                    pNode.lnum = erasedNode.lnum;
                    fixNodeParent.lnum--;
                }
                if (root == erasedNode)
                {
                    root = pNode;
                }
                else if (erasedNode.parent.left == erasedNode)
                {
                    erasedNode.parent.left = pNode;
                }
                else
                {
                    erasedNode.parent.right = pNode;
                }
                pNode.parent = erasedNode.parent;
                dec_num(fixNodeParent);
                var tcol = pNode.state;
                pNode.state = erasedNode.state;
                erasedNode.state = tcol;
            }
            if (Node.state0 == erasedNode.state)
            {
                for (; fixNode != root && Node.state0 == fixNode.state; fixNodeParent = fixNode.parent)
                {
                    if (fixNode == fixNodeParent.left)
                    {
                        pNode = fixNodeParent.right;
                        if (Node.state1 == pNode.state)
                        {
                            pNode.state = Node.state0;
                            fixNodeParent.state = Node.state1;
                            left_rotate(fixNodeParent);
                            pNode = fixNodeParent.right;
                        }
                        if (is_nil(pNode))
                        {
                            fixNode = fixNodeParent;
                        }
                        else if (Node.state0 == pNode.left.state && Node.state0 == pNode.right.state)
                        {
                            pNode.state = Node.state1;
                            fixNode = fixNodeParent;
                        }
                        else
                        {
                            if (Node.state0 == pNode.right.state)
                            {
                                pNode.left.state = Node.state0;
                                pNode.state = Node.state1;
                                right_rotate(pNode);
                                pNode = fixNodeParent.right;
                            }
                            pNode.state = fixNodeParent.state;
                            fixNodeParent.state = Node.state0;
                            pNode.right.state = Node.state0;
                            left_rotate(fixNodeParent);
                            break;
                        }
                    }
                    else
                    {
                        pNode = fixNodeParent.left;
                        if (Node.state1 == pNode.state)
                        {
                            pNode.state = Node.state0;
                            fixNodeParent.state = Node.state1;
                            right_rotate(fixNodeParent);
                            pNode = fixNodeParent.left;
                        }
                        if (is_nil(pNode))
                        {
                            fixNode = fixNodeParent;
                        }
                        else if (Node.state0 == pNode.right.state && Node.state0 == pNode.left.state)
                        {
                            pNode.state = Node.state1;
                            fixNode = fixNodeParent;
                        }
                        else
                        {
                            if (Node.state0 == pNode.left.state)
                            {
                                pNode.right.state = Node.state0;
                                pNode.state = Node.state1;
                                left_rotate(pNode);
                                pNode = fixNodeParent.left;
                            }
                            pNode.state = fixNodeParent.state;
                            fixNodeParent.state = Node.state0;
                            pNode.left.state = Node.state0;
                            right_rotate(fixNodeParent);
                            break;
                        }
                    }
                }
                fixNode.state = Node.state0;
            }
            erasedNode.parent = erasedNode.left = erasedNode.right = null;
            erasedNode.lnum = erasedNode.rnum = 0;
        }

        Node max(Node pNode)
        {
            while (!is_nil(pNode.right))
            {
                pNode = pNode.right;
            }
            return pNode;
        }

        Node min(Node pNode)
        {
            while (!is_nil(pNode.left))
            {
                pNode = pNode.left;
            }
            return pNode;
        }

        Node next(Node ptr)
        {
            if (is_nil(ptr))
            {
                return ptr;
            }
            else if (!is_nil(ptr.right))
            {
                return min(ptr.right);
            }
            else
            {
                Node pNode;
                while (!is_nil(pNode = ptr.parent) && ptr == pNode.right)
                {
                    ptr = pNode;
                }
                return pNode;
            }
        }

        Node previous(Node ptr)
        {
            if (is_nil(ptr))
            {
                return ptr;
            }
            else if (!is_nil(ptr.left))
            {
                return max(ptr.left);
            }
            else
            {
                Node pNode;
                while (!is_nil(pNode = ptr.parent) && ptr == pNode.left)
                {
                    ptr = pNode;
                }
                return pNode;
            }
        }

        void erase(Node rootNode)
        {
            for (Node pNode = rootNode; !is_nil(pNode); rootNode = pNode)
            {
                erase(pNode.right);
                pNode = pNode.left;
                rootNode.parent = rootNode.left = rootNode.right = null;
            }
        }

        public void Clear()
        {
            _change++;
            erase(root);
            root = lmost = rmost = _head;
        }

        public Node Find(int index)
        {
            int leftCount = 0;
            Node pNode = root;
            Node whereNode = _head;
            while (!is_nil(pNode))
            {
                int count = pNode.lnum + leftCount;
                if (count < index)
                {
                    leftCount += pNode.lnum + 1;
                    pNode = pNode.right;
                }
                else if (count > index)
                {
                    whereNode = pNode;
                    pNode = pNode.left;
                }
                else
                {
                    whereNode = pNode;
                    break;
                }
            }
            return !is_nil(whereNode) ? whereNode : null;
        }

        public Node Insert(int index, TValue value)
        {
            return insert(index, value);
        }

        public void Insert(int index, Node value)
        {
            insert(index, value);
        }

        public void AddFirst(Node value)
        {
            insert_at(true, lmost, value);
        }

        public Node AddFirst(TValue value)
        {
            Node newNode = new_inter_node(value);
            AddFirst(newNode);
            return newNode;
        }

        public void AddLast(Node value)
        {
            insert_at(false, rmost, value);
        }

        public Node AddLast(TValue value)
        {
            Node newNode = new_inter_node(value);
            AddLast(newNode);
            return newNode;
        }

        public Node Remove(int index)
        {
            Node find = Find(index);
            if (null != find)
            {
                remove(find);
            }
            return find;
        }

        public void Remove(Node where)
        {
            remove(where);
        }

        public Node RemoveFirst()
        {
            Node where = lmost;
            if (!is_nil(where))
            {
                remove(where);
            }
            return where;
        }

        public Node RemoveLast()
        {
            Node where = rmost;
            if (!is_nil(where))
            {
                remove(where);
            }
            return where;
        }

        public int Index(Node node)
        {
            if (null == node)
            {
                return -1;
            }
            int count = -1;
            Node pNode = node;
            while (!is_nil(pNode))
            {
                Node parent = pNode.parent;
                if (is_nil(parent) || parent.right == pNode)
                {
                    count += pNode.lnum + 1;
                }
                else
                {
                    count -= pNode.rnum;
                }
                pNode = parent;
            }
            return count;
        }

        public TValue this[int index]
        {
            get
            {
                return Find(index).Value;
            }
            set
            {
                Find(index).Value = value;
            }
        }

        public IEnumerator<TValue> GetEnumerator()
        {
            int change = _change;
            Node it = lmost;
            while (!is_nil(it))
            {
                yield return it.value;
                if (change != _change)
                {
                    break;
                }
                it = next(it);
            }
            yield break;
        }

        public int Count
        {
            get
            {
                return root.lnum + root.rnum;
            }
            set
            {
                while (Count < value)
                {
                    AddLast(default(TValue));
                }
                while (Count > value)
                {
                    RemoveLast();
                }
            }
        }

        public TValue[] ToArray()
        {
            int idx = 0;
            TValue[] array = new TValue[Count];
            Node it = lmost;
            while (!is_nil(it))
            {
                array[idx++] = it.value;
                it = next(it);
            }
            return array;
        }

        public List<TValue> ToList()
        {
            List<TValue> list = new List<TValue>(Count);
            Node it = lmost;
            while (!is_nil(it))
            {
                list.Add(it.value);
                it = next(it);
            }
            return list;
        }

        public Node Next(Node node)
        {
            Node it = next(node);
            return is_nil(it) ? null : it;
        }

        public Node Prev(Node node)
        {
            Node it = previous(node);
            return is_nil(it) ? null : it;
        }

        public Node First
        {
            get
            {
                return is_nil(lmost) ? null : lmost;
            }
        }

        public Node Last
        {
            get
            {
                return is_nil(rmost) ? null : rmost;
            }
        }
    }

    public class MsgQueue<T>
    {
        public class Node
        {
            internal T _value;
            internal Node _next;

            public Node(T value)
            {
                _value = value;
                _next = null;
            }

            public T Value
            {
                get
                {
                    return _value;
                }
                set
                {
                    _value = value;
                }
            }
        }

        int _count;
        Node _head;
        Node _tail;

        public MsgQueue()
        {
            _count = 0;
            _head = _tail = null;
        }

        public void AddLast(T value)
        {
            AddLast(new Node(value));
        }

        public void AddFirst(T value)
        {
            AddFirst(new Node(value));
        }

        public void AddLast(Node node)
        {
            if (null == _tail)
            {
                _head = node;
            }
            else
            {
                _tail._next = node;
            }
            node._next = null;
            _tail = node;
            _count++;
        }

        public void AddFirst(Node node)
        {
            node._next = _head;
            _head = node;
            if (0 == _count++)
            {
                _tail = node;
            }
        }

        public void RemoveFirst()
        {
            _head = _head._next;
            if (0 == --_count)
            {
                _tail = null;
            }
        }

        public void Clear()
        {
            _count = 0;
            _head = _tail = null;
        }

        public Node First
        {
            get
            {
                return _head;
            }
        }

        public Node Last
        {
            get
            {
                return _tail;
            }
        }

        public int Count
        {
            get
            {
                return _count;
            }
        }
    }
}
